{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Restore The Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfArrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #恢复数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 <code>[1, k]</code>&nbsp;之间，且数组中的数字都没有前导 0 。</p>\n",
    "\n",
    "<p>给你字符串&nbsp;<code>s</code>&nbsp;和整数&nbsp;<code>k</code>&nbsp;。可能会有多种不同的数组恢复结果。</p>\n",
    "\n",
    "<p>按照上述程序，请你返回所有可能输出字符串&nbsp;<code>s</code>&nbsp;的数组方案数。</p>\n",
    "\n",
    "<p>由于数组方案数可能会很大，请你返回它对&nbsp;<code>10^9 + 7</code>&nbsp;<strong>取余</strong>&nbsp;后的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;1000&quot;, k = 10000\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>唯一一种可能的数组方案是 [1000]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;1000&quot;, k = 10\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不存在任何数组方案满足所有整数都 &gt;= 1 且 &lt;= 10 同时输出结果为 s 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;1317&quot;, k = 2000\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>可行的数组方案为 [1317]，[131,7]，[13,17]，[1,317]，[13,1,7]，[1,31,7]，[1,3,17]，[1,3,1,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;2020&quot;, k = 30\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>唯一可能的数组方案是 [20,20] 。 [2020] 不是可行的数组方案，原因是 2020 &gt; 30 。 [2,020] 也不是可行的数组方案，因为 020 含有前导 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;1234567890&quot;, k = 90\n",
    "<strong>输出：</strong>34\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code>.</li>\n",
    "\t<li><code>s</code>&nbsp;只包含数字且不包含前导 0 。</li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10^9</code>.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [restore-the-array](https://leetcode.cn/problems/restore-the-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [restore-the-array](https://leetcode.cn/problems/restore-the-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1000\"\\n10000', '\"1000\"\\n10', '\"1317\"\\n2000']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        sl=[int(x) for x in s]\n",
    "        n=len(s)\n",
    "        m=len(str(k))\n",
    "        dp=[0]*n\n",
    "\n",
    "        if 0<sl[0]<=k:\n",
    "            dp[0]=1\n",
    "        else:\n",
    "            return 0\n",
    "        mod=10**9+7\n",
    "        for i in range(1,n):\n",
    "            if 0<sl[i]<=k:\n",
    "                dp[i]+=dp[i-1]\n",
    "            cur=sl[i]\n",
    "            for j in range(1,m):\n",
    "                if i-j>=0 and sl[i-j]!=0:\n",
    "                    cur+= sl[i-j]*(10**j)\n",
    "                    if cur<=k:\n",
    "                        if i-j-1>=0:\n",
    "                            dp[i]+=dp[i-j-1]\n",
    "                        else:\n",
    "                            dp[i]+=1\n",
    "                    else:\n",
    "                        break\n",
    "            if dp[i]==0:\n",
    "                return 0\n",
    "            dp[i]%=mod\n",
    "        # print(dp)\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = int(10 ** 9 + 7)\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[-1] = 1\n",
    "        j = n\n",
    "        accum = list(dp)\n",
    "        accum.append(0)\n",
    "        sl = len(str(k))\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0':\n",
    "                dp[i] = 0\n",
    "                accum[i] = accum[i + 1]\n",
    "                continue\n",
    "            j = max(i + 1, min(j, i + sl))\n",
    "            while j > i and int(s[i:j]) > k:\n",
    "                j -= 1\n",
    "            dp[i] = accum[i + 1] - accum[j + 1]\n",
    "            dp[i] %= mod\n",
    "            accum[i] = (dp[i] + accum[i + 1]) % mod\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        dp = defaultdict(int)\n",
    "        dp[-1] = 1\n",
    "        len_k = len(str(k))\n",
    "        mod_number = 10 ** 9 + 7\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i, max(-1, i - len_k), -1):\n",
    "                if s[j] != '0' and int(s[j:i + 1]) <= k:\n",
    "                    dp[i] += dp[j - 1]\n",
    "            dp[i] %= mod_number\n",
    "        return dp[len(s) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        c = [[1]]\n",
    "        \n",
    "        for i, j in enumerate(s):\n",
    "            c.append([])\n",
    "            c[-1].append(c[-2][0])\n",
    "\n",
    "            for x, y in enumerate(c[-2]):\n",
    "                if x == 0 and j == '0':\n",
    "                    c[-1].append(0)\n",
    "                    continue\n",
    "\n",
    "                if int(s[i - x: i + 1]) > k:\n",
    "                    c[-1].append(0)\n",
    "                else:\n",
    "                    c[-1].append(y)\n",
    "\n",
    "            while c and c[-1][-1] == 0:\n",
    "                c[-1].pop(-1)\n",
    "\n",
    "            if len(c[-1]) == 1:\n",
    "                return 0\n",
    "            c[-1][0] = sum(c[-1][1:]) % (10 ** 9 + 7)\n",
    "\n",
    "        return c[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        N = len(s)\n",
    "        M = len(str(k))\n",
    "        YU = 10**9+7\n",
    "        dp = [[0]*M for _ in range(N)]\n",
    "        for i in range(min(N, M)):\n",
    "            if int(s[:i + 1]) <= k:\n",
    "                dp[i][i] = 1\n",
    "\n",
    "        for i in range(1, N):\n",
    "            for j in range(min(M-1, i+1)):\n",
    "                if s[i-j] != '0':\n",
    "                    dp[i][j] = sum(dp[max(0, i-j-1)])%YU\n",
    "            if i-M >= 0 and int(s[i-M+1:i+1]) <= k:\n",
    "                if s[i - M + 1] != '0':\n",
    "                    dp[i][M-1] = sum(dp[i-M])%YU\n",
    "\n",
    "        return sum(dp[-1])%YU"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n, m = len(s), len(str(k))\n",
    "        dp = [[0] * (11) for _ in range(n + 1)]\n",
    "        if int(s[0]) > k: return 0\n",
    "        \n",
    "        dp[0][1] = 1\n",
    "        i = 1\n",
    "        while i < n:\n",
    "            if s[i] == '0':\n",
    "                while i < n and s[i] == '0': i += 1\n",
    "                i -= 1\n",
    "            j = i\n",
    "            st, pw = 0, 1\n",
    "            while j >= max(0, i - m + 1):\n",
    "                while j >= max(0, i - m + 1) and s[j] == '0': \n",
    "                    j -= 1\n",
    "                    pw *= 10\n",
    "                st += int(s[j]) * pw\n",
    "\n",
    "                if st > k or st == 0 or s[j] == '0': break\n",
    "                \n",
    "                dp[i][i - j + 1] = (dp[i][i - j + 1] + 1 if j == 0 else sum(dp[j - 1])) % MOD\n",
    "                j -= 1\n",
    "                pw *= 10\n",
    "            i += 1\n",
    "        return sum(dp[n - 1]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        len_k=len(str(k))\n",
    "        @functools.cache\n",
    "        def dp(index):\n",
    "            if index>=0:\n",
    "                temp_cases=0\n",
    "                min_i=max(-1,index-len_k)+1\n",
    "                for i in range(min_i,index+1):\n",
    "                    if i==min_i and int(s[i:index+1])>k: continue\n",
    "                    if s[i]==\"0\": continue\n",
    "                    temp_cases+=dp(i-1)\n",
    "                return temp_cases%MOD\n",
    "            else:\n",
    "                return 1\n",
    "        return dp(len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.MODULO = 10 ** 9 + 7\n",
    "\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        sSize = len(s)\n",
    "\n",
    "        # dp[i] is the number of ways you can divide the string starting from index i to the end.\n",
    "        dp = [0] * (sSize + 1)\n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(0, sSize):\n",
    "            if s[i] == '0':\n",
    "                continue\n",
    "\n",
    "            for j in range(i+1, sSize+1):\n",
    "                if int(s[i:j]) > k:\n",
    "                    break\n",
    "\n",
    "                dp[j] += dp[i]\n",
    "\n",
    "            dp[i] %= self.MODULO\n",
    "\n",
    "        retVal = dp[-1] % self.MODULO\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "\n",
    "        # 检查字符串是否合法\n",
    "        @lru_cache(None)\n",
    "        def check(st):\n",
    "            if st[0] == \"0\":\n",
    "                return False\n",
    "            return 1 <= int(st) <= k\n",
    "\n",
    "        # 计算上界的长度即目标字符串的最大长度\n",
    "        m = len(str(k))\n",
    "        # 初始化\n",
    "        n = len(s)\n",
    "        dp = [1, int(check(s[0]))]\n",
    "        for i in range(1, n):\n",
    "            cnt = 0\n",
    "            # 枚举以i结尾的长度为j的字符的组合数\n",
    "            for j in range(1, m+1):\n",
    "                if j > len(dp):\n",
    "                    break\n",
    "                if check(s[i-j+1: i+1]):\n",
    "                    cnt += dp[-j]\n",
    "            cnt %= MOD\n",
    "            dp.append(cnt)\n",
    "            # 往前最多回溯m个长度因此dp长度最大也为m\n",
    "            if len(dp) > m:\n",
    "                dp.pop(0)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        return self.search(s, str(k), 0, {})\n",
    "\n",
    "    def search(self, s, k, i, table):\n",
    "        if i not in table:\n",
    "            n = len(s)\n",
    "            if i == n:\n",
    "                table[i] = 1\n",
    "            elif i > n:\n",
    "                table[i] = 0\n",
    "            else:\n",
    "                if s[i] == '0':\n",
    "                    table[i] = 0\n",
    "                else:\n",
    "                    res = 0\n",
    "                    l = len(k)\n",
    "                    for j in range(l - 1):\n",
    "                        res += self.search(s, k, i + j + 1, table)\n",
    "                    if i + l <= n and s[i: i + l] <= k:\n",
    "                        res += self.search(s, k, i + l, table)\n",
    "                    table[i] = res % int(1e9 + 7)\n",
    "        return table[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(s)\n",
    "        m = [0] * n\n",
    "        def backtrack(idx):\n",
    "            \n",
    "            if idx == n:\n",
    "                return 1\n",
    "\n",
    "            if m[idx]:\n",
    "                return m[idx]\n",
    "\n",
    "            if s[idx]==\"0\":\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            end = idx+1\n",
    "            while end<=n and int(s[idx:end])<=k:\n",
    "                res += backtrack(end)\n",
    "                end += 1\n",
    "            res %= mod\n",
    "            m[idx] = res\n",
    "            return res\n",
    "        return backtrack(0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        n = len(s)\n",
    "        dp = [-1] * (n + 1)\n",
    "        for i in range(n):\n",
    "            if s[i] == '0':\n",
    "                dp[i] = 0\n",
    "        dp[n] = 1\n",
    "\n",
    "\n",
    "        def process(i: int) -> int:\n",
    "            if dp[i] >= 0:\n",
    "                return dp[i]\n",
    "\n",
    "            # if i == n:\n",
    "            #     return 1\n",
    "            # elif s[i] == '0':\n",
    "            #     return 0\n",
    "            \n",
    "            val, total = 0, 0\n",
    "            for j in range(i, n):\n",
    "                val = val * 10 + int(s[j])\n",
    "                if val > k:\n",
    "                    break\n",
    "                total += process(j + 1)\n",
    "            dp[i] = total % MOD\n",
    "            return dp[i]\n",
    "\n",
    "\n",
    "        return process(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        memo = [-1] * len(s)\n",
    "        mod = 1e9 + 7\n",
    "\n",
    "        def dfs(i):\n",
    "            \"\"\"\n",
    "            dfs(i) is the num of possible arrays base and s[0]~s[i] and k\n",
    "            \"\"\"\n",
    "            # i = 0, means s is [elem], return 1\n",
    "            if i < 0:\n",
    "                return 1\n",
    "            \n",
    "            if memo[i] != -1:\n",
    "                return memo[i]\n",
    "\n",
    "            res = 0\n",
    "            base = 1 \n",
    "            currNum = 0\n",
    "            for j in range(i, -1, -1):\n",
    "                # currNum += (ord(s[j])-ord('0')) * base\n",
    "                currNum = int(s[j]) * base + currNum\n",
    "                base *= 10\n",
    "                if currNum > k:\n",
    "                    break\n",
    "                if s[j] != \"0\":\n",
    "                    res += dfs(j - 1)\n",
    "\n",
    "            memo[i] = res % mod\n",
    "            return res % mod\n",
    "        \n",
    "        return int(dfs(len(s) - 1))\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        @lru_cache\n",
    "        def dfs(j: int) -> int:\n",
    "            if j == 0: return 1\n",
    "            ans = 0\n",
    "            for i in range(j - 1, max(-1, j - 12), -1):\n",
    "                if s[i] == '0': continue\n",
    "                if int(s[i: j]) <= k: ans += dfs(i)\n",
    "            return ans % MOD\n",
    "        \n",
    "        return dfs(len(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        # 设置cache空间，避免出现内存溢出\n",
    "        # cache空间必须设置，若不设置cache，执行时间超时\n",
    "        # 目前的执行时间仅超过10左右。应该有优化空间\n",
    "        @lru_cache(maxsize = 10 ** 1)\n",
    "        def nums(begin) :\n",
    "            if begin == n: return 1\n",
    "            if s[begin] == '0':\n",
    "                return 0\n",
    "            ret = 0\n",
    "            for i in range(1, min(n-begin, len(str(k)))+1):\n",
    "                if int(s[begin:begin + i]) <= k:\n",
    "                    ret += nums(begin+i)\n",
    "            return ret % (10 ** 9 + 7)\n",
    "\n",
    "        return nums(0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 1408 ms ... 49 % ... 141.1 MB ... 36 %\n",
    "        #  time: O(n)\n",
    "        # space: O(n)\n",
    "        \n",
    "        seen = {}\n",
    "        def func(sidx):    # 返回 s[sidx:] 的方案总数\n",
    "            if sidx == len(s):\n",
    "                return 1\n",
    "            if s[sidx] == '0':\n",
    "                return 0\n",
    "            if sidx not in seen:\n",
    "                res, val = 0, 0\n",
    "                for eidx in range(sidx, len(s)):\n",
    "                    val = val * 10 + int(s[eidx])\n",
    "                    if val > k:\n",
    "                        break\n",
    "                    res += func(eidx + 1)\n",
    "                seen[sidx] = res % mod\n",
    "            return seen[sidx]\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        return func(0)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        def dfs(st):\n",
    "            if st==len(s):\n",
    "                return 1\n",
    "            if s[st]=='0':\n",
    "                return 0\n",
    "            if st in dp:\n",
    "                return dp[st]\n",
    "            ret=0\n",
    "            for i in range(1,len(ks)+1):\n",
    "                if st+i>len(s):\n",
    "                    break\n",
    "                v=int(s[st:(st+i)])\n",
    "                if v>=1 and v<=k:\n",
    "                    ret=(ret+dfs(st+i))%mod\n",
    "            dp[st]=ret\n",
    "            return ret\n",
    "        \n",
    "        ks=str(k)\n",
    "        dp={}\n",
    "        mod=10**9+7\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        # 以i为字符串起点的方案数\n",
    "        @lru_cache(typed=False, maxsize=len(s))\n",
    "        def dfs(i):\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "            if s[i] == '0':\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            for j in range(i, len(s)):\n",
    "                if int(s[i : j + 1]) > k:\n",
    "                    break\n",
    "                res += dfs(j + 1)% MOD\n",
    "            return res\n",
    "\n",
    "        res = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        MOD = pow(10,9) + 7\n",
    "        @cache\n",
    "        def dfs(p):\n",
    "            if p < 0:\n",
    "                p = 0\n",
    "            t =  ord(s[p]) - ord('0')\n",
    "            if p == 0:\n",
    "                return 1 if t < k and t != 0  else 0\n",
    "            res = 0\n",
    "            now = 0\n",
    "            base = 1\n",
    "            while p >= 0:\n",
    "                now += (ord(s[p]) - ord('0')) * base\n",
    "                base *= 10\n",
    "                if now > k:\n",
    "                    break\n",
    "                if s[p] != '0':\n",
    "                    res += dfs(p-1)\n",
    "                    res %= MOD\n",
    "                p -= 1\n",
    "            return res\n",
    "        return dfs(len(s)-1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        MOD = int(1e9+7)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                return 1\n",
    "            ret = 0\n",
    "            base = 1\n",
    "            val = 0\n",
    "            for j in range(i, -1, -1):\n",
    "                val = int(s[j]) * base + val\n",
    "                base *= 10\n",
    "                if val > k:\n",
    "                    break\n",
    "                if s[j] != '0':\n",
    "                    ret += dfs(j-1)\n",
    "                    ret %= MOD\n",
    "            \n",
    "            return ret\n",
    "\n",
    "        return dfs(len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        @cache\n",
    "        def g(i):\n",
    "            if i==n:\n",
    "                return 1\n",
    "            res=0    \n",
    "            for j in range(i,n):\n",
    "                if s[i]=='0':\n",
    "                    break\n",
    "                if int(s[i:j+1])>k:\n",
    "                    break\n",
    "                res+=g(j+1)\n",
    "            return res%(10**9+7)\n",
    "        return g(0)%(10**9+7)            \n",
    "\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        # [1,k] 之间\n",
    "        n = len(s)\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            m = ''\n",
    "            for j in range(i,n):\n",
    "                if m =='' and s[j] == '0':\n",
    "                    break\n",
    "                m += s[j] \n",
    "                if not 1<= int(m) <=k:\n",
    "                    break \n",
    "                res += dfs(j+1)\n",
    "            return res%MOD\n",
    "        return dfs(0)%MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        MOD = 10**9 +7\n",
    "        n = len(s)\n",
    "        # 以 i 为字符串起点的方案数\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == n:\n",
    "                return 1\n",
    "            if s[i] == '0':\n",
    "                return 0\n",
    "            res = 0\n",
    "            for j in range(i, n):\n",
    "                if int(s[i:j+1]) > k:\n",
    "                    break\n",
    "                res += dfs(j + 1) % MOD\n",
    "            return res\n",
    "        return dfs(0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def f(self, p):\n",
    "        if p>=len(self.s) or self.s[p]=='0': return 0\n",
    "        i, res = 1, 0\n",
    "        while int(self.s[p:p+i])<=self.k and p+i<=len(self.s):\n",
    "            res += self.f(p+i)\n",
    "            i += 1\n",
    "        return (res+(int(self.s[p:p+self.x+1])<=self.k)) %1000000007      \n",
    "\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        self.s, self.k, self.x = s, k, len(str(k))\n",
    "        return self.f(0)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dp(left, right):\n",
    "            if left > right:\n",
    "                return 1\n",
    "            if s[left] == '0':\n",
    "                return 0\n",
    "            count = 0\n",
    "            for i in range(left, right + 1):\n",
    "                if int(s[left:i + 1]) > k:\n",
    "                    break\n",
    "                count = (count + dp(i + 1, right)) % MOD\n",
    "            return count\n",
    "        \n",
    "        n = len(s)\n",
    "        return dp(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        n = len(s) \n",
    "        A = [int(ch) for ch in s] + [1]\n",
    "        k = str(k) \n",
    "        m = len(k) \n",
    "        @cache \n",
    "        def f(n):\n",
    "            if n <= 0 : return int(n==0)\n",
    "            if A[n] == 0 : return f(n-1) \n",
    "            if n < m or s[n-m:n] <= k : \n",
    "                return (f(n-1) * 2 - f(n-m-1)) % 1000000007\n",
    "            return (f(n-1) * 2 - f(n-m)) % 1000000007\n",
    "        return (f(n)-f(n-1))  % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        n = len(s)\n",
    "        pairs = dict()\n",
    "        for l in range(n):\n",
    "            if s[l] != '0':\n",
    "                left, right = l, min(int(math.log10(k))+1+l, n+1)\n",
    "                mid = right\n",
    "                while right-left > 1:\n",
    "                    r = mid\n",
    "                    if 1 <= int(s[l:r]) <= k:\n",
    "                        left = mid\n",
    "                        mid = (left+right)//2\n",
    "                    else:\n",
    "                        right = mid\n",
    "                        mid = (left+right)//2\n",
    "                if 1 <= int(s[l:r]) <= k:\n",
    "                    pairs[l] = r\n",
    "                else:\n",
    "                    pairs[l] = r\n",
    "        \n",
    "        @lru_cache(200000)\n",
    "        def help(m):\n",
    "            if m == n:\n",
    "                return 1\n",
    "            if m not in pairs.keys():\n",
    "                return 0\n",
    "            s = 0\n",
    "            for i in range(m+1, pairs[m]+1):\n",
    "                s += help(i)\n",
    "            return s% (10**9+7)\n",
    "        \n",
    "        return help(0) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "# 某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，\n",
    "# 我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导 0 。\n",
    "# 1 <= s.length <= 10^5.\n",
    "\n",
    "# lru 超时 改用手动memo ？？？\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        # 以i为字符串起点的方案数\n",
    "        @lru_cache(typed=False, maxsize=20000)\n",
    "        def dfs(i):\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "            if s[i] == '0':\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            for j in range(i, len(s)):\n",
    "                if int(s[i : j + 1]) > k:\n",
    "                    break\n",
    "                res += dfs(j + 1)\n",
    "            return res\n",
    "\n",
    "        res = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        limit = str(k)\n",
    "\n",
    "        @lru_cache(maxsize=8192)\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "\n",
    "            t = 0\n",
    "            if i - len(limit) >= 0:\n",
    "                if s[i - len(limit)] != '0' and s[i - len(limit):i] <= limit:\n",
    "                    t += dfs(i - len(limit))\n",
    "                for j in range(i - len(limit) + 1, i):\n",
    "                    if s[j] != '0':\n",
    "                        t += dfs(j)\n",
    "            else:\n",
    "                for j in range(i):\n",
    "                    if s[j] != '0':\n",
    "                        t += dfs(j)\n",
    "            return t\n",
    "\n",
    "        ans = dfs(len(s))\n",
    "        ans %= 10**9+7\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = len(s)\n",
    "        lk = len(str(k))\n",
    "        dp = [0]*n + [1]\n",
    "        for now in range(n-1, -1, -1):\n",
    "            if s[now] != '0':\n",
    "                for end in range(now+1, min(now+lk+1, n+1)):\n",
    "                    if int(s[now: end]) <= k:\n",
    "                        dp[now] += dp[end]\n",
    "        return dp[0] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        t=len(str(k))\n",
    "        ss=[[0,1]]\n",
    "        sett=0\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i]=='0':\n",
    "                sett+=1\n",
    "            else:\n",
    "                pp=int(s[i])*(10**sett)\n",
    "                kkk=sett\n",
    "                sett=0\n",
    "                if pp<=k:\n",
    "                    ss.append([pp,1])\n",
    "                    break\n",
    "                else:\n",
    "                    return 0\n",
    "        for i in range(len(s)-kkk-2,-1,-1):\n",
    "            if s[i]=='0':\n",
    "                sett+=1\n",
    "            else:\n",
    "                pp=int(s[i])*(10**sett)\n",
    "                sett=0\n",
    "                key=ss[-1][1]\n",
    "                p=t-len(str(pp))\n",
    "                qwer=str(pp)\n",
    "                if pp>k:\n",
    "                    return 0\n",
    "                for j in range(1,p+2):\n",
    "                    \n",
    "                    if j<len(ss) and int(qwer+str(ss[-j][0]))<=k:\n",
    "                        qwer=qwer+str(ss[-j][0])\n",
    "                        key+=ss[-j-1][1]\n",
    "                    else:\n",
    "                        break\n",
    "                ss.append([pp,key])\n",
    "        if sett!=0:\n",
    "            return 0\n",
    "        return ss[-1][1]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, prev):\n",
    "        #     if i == n:\n",
    "        #         return 1 if 1 <= int(s[prev:]) <= k else 0\n",
    "\n",
    "        #     if 1 <= int(s[prev:i]) <= k:\n",
    "        #         return dfs(i + 1, prev) + dfs(i + 1, i)\n",
    "        #     return 0\n",
    "        \n",
    "        # return dfs(1, 0) % MOD\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "\n",
    "        for prev in range(max(0, n - 10), n):\n",
    "            f[prev] = 1 if 1 <= int(s[prev:]) <= k else 0\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for prev in range(max(0, i - 10), i):\n",
    "                if 1 <= int(s[prev:i]) <= k:\n",
    "                    f[prev] = f[prev] + f[i]\n",
    "                else:\n",
    "                    f[prev] = 0\n",
    "        return f[0] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArrays(self, s: str, k: int) -> int:\n",
    "        # 与密码解密类似，穷举s末尾的所有可能数字，(范围[1,k])\n",
    "        MOD = 10**9+7\n",
    "        n = len(s)\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 1\n",
    "        bit = len(str(k))\n",
    "        for i in range(1,n+1):\n",
    "            flag = False\n",
    "            for j in range(i-1, i-bit-1, -1):\n",
    "                if j<0: break\n",
    "                cur = s[j:i]\n",
    "                if cur[0] == '0':\n",
    "                    continue\n",
    "                if int(cur)<=k:\n",
    "                    dp[i] = dp[i] + dp[j]\n",
    "                    flag = True\n",
    "            if not flag: return 0\n",
    "        return dp[-1]%MOD"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
